package com.hardy.data_structure;

/**
 * Author: Hardy
 * Date:   2019/3/21
 * Description:
 **/
public class Main {

    public static void main(String[] args) {
//        testArray();
//        testSingleLinked();
//        testDoubleLinked();
        testSingleLinkedFunc();
    }

    private static void testArray() {
        Array a = new Array();
        a.print();

        a.add(0);
        a.add(1);
        a.print();

        a.add(2);
        a.add(3);
        a.add(4);
        a.add(5);
        a.print();

        a.del(1);
        a.print();

        a.del(2);
        a.print();

        System.out.println("==========================================");

        a.insert(1, 1);
        a.print();

        a.insert(2, 2);
        a.print();

        a.remove(2);
        a.print();

        a.remove(1);
        a.print();
    }

    private static void testSingleLinked() {
        Linked linked = new SingleLinked();
        linked.print();

        linked.add(0);
        linked.print();

        linked.add(1);
        linked.add(2);
        linked.print();

        linked.del(1);
        linked.print();

        linked.del(2);
        linked.print();

        linked.del(0);
        linked.print();

        System.out.println("===================");

        // 首次
        linked.insert(0, 0);
        linked.print();

        // 头
        linked.insert(0, -1);
        linked.print();

        // 尾
        linked.insert(2, 2);
        linked.print();

        // 中间
        linked.insert(2, 1);
        linked.print();


        // 中间
        linked.remove(2);
        linked.print();

        // 尾部
        linked.remove(2);
        linked.print();

        // 头部
        linked.remove(0);
        linked.print();

        // 最后一个
        linked.remove(0);
        linked.print();

        System.out.println("=========================");
        linked.reverse();
        linked.print();

        linked.add(0);
        linked.add(1);
        linked.reverse();
        linked.print();

        linked.add(2);
        linked.add(3);
        linked.add(4);
        linked.reverse();
        linked.print();
    }

    private static void testDoubleLinked() {
        DoubleLinked linked = new DoubleLinked();
        linked.add(0);
        linked.print();

        linked.add(1);
        linked.add(2);
        linked.add(3);
        linked.print();

        linked.del(-1);
        linked.print();

        linked.del(1);
        linked.print();

        linked.del(0);
        linked.print();

        linked.del(3);
        linked.print();

        linked.del(2);
        linked.print();

        // 插入
        linked.insert(1, 1);
        linked.print();

        // 头插
        linked.insert(0, 1);
        linked.insert(0, 0);
        linked.print();

        // 尾插
        linked.insert(2, 3);
        linked.print();

        // 中插
        linked.insert(2, 2);
        linked.print();

        // 中删
        linked.remove(2);
        linked.print();

        // 尾删
        linked.remove(2);
        linked.print();

        // 头删除
        linked.remove(0);
        linked.print();

        // 删完
        linked.remove(0);
        linked.print();


//        linked.reverse();
//        linked.print();
//
//        linked.add(0);
//        linked.add(1);
//        linked.reverse();
//        linked.print();
//
//        linked.add(2);
//        linked.reverse();
//        linked.print();
    }

    private static void testSingleLinkedFunc() {
        checkMerge();
    }

    private static void checkCircle() {
        SingleLinked linked = new SingleLinked();
        linked.add(0);
        linked.add(1);
        linked.add(2);
        linked.add(3);
        linked.add(4);

        System.out.println(linked.checkCircle());

        // 环
        linked.root.next.next.next.next = linked.root.next.next;

        System.out.println(linked.checkCircle());
    }

    private static void checkMerge() {
        SingleLinked p = new SingleLinked();
        p.add(0);
        p.add(2);
        p.add(3);

        SingleLinked q = new SingleLinked();
        q.add(0);
        q.add(1);
        q.add(5);

        SingleLinked linked = new SingleLinked();
        linked.root = merge(p.root, q.root);
        linked.print();
    }

    private static Node merge(Node p, Node q) {
        if (p == null || q == null) return null;

        Node root = null;
        // 找头
        if (p.val > q.val) {
            root = q;
            q = q.next;
        } else {
            root = p;
            p = p.next;
        }

        Node node = root;

        // 合并
        while (p != null && q != null) {
            if (p.val > q.val) {
                node.next = q;
                q = q.next;
            } else {
                node.next = p;
                p = p.next;
            }
            node = node.next;
        }

        if (p == null) {
            node.next = q;
        } else {
            node.next = p;
        }

        return root;
    }
}
